from adt.tree import Tree
from compilers.basics import ParseError, Token
from compilers.operator_based import FormalOperator, FormalOperand


class Stack(list):
    """
    Just some syntactic sugar for stack operations, implemented
    via a list.
    """
    def push(self, value):
        self.append(value)
    def top(self):
        return self[-1]


class Calculator(object):
    """
    The Calculator is an operator-based parser in which the language
    description comprises of operands types (instances of FormalOperand)
    and operator (instances of FormalOperator). Operators have a priority
    which induces evaluation order, as well as arity which is split into
    left-arity (the number of operands to the left of the operator) and
    right-arity (the number of operands to the right). The operands themselves
    need not conform to any specified interface.
    The input to the calculator is a stream of Token objects, the 'kind'
    attribute of each is either a FormalOperand or a FormalOperator. Tokens
    are processed using a stack, where the eventual output produced by the
    parsing is an expression tree corresponding to the expression represented
    by the input.
    ParseError is raised if the input is not a valid expression in the
    operator language described.
    """
    
    SEP = "|"
    
    def __init__(self):
        self.operand_stack = Stack()
        self.operator_stack = Stack()
        
    def process(self, iterable):
        """
        Processes a stream of tokens. It is possible to invoke process()
        several times to digest a long stream, state is conserved between
        calls.
        @param iterable an iterable object over Token objects
        """
        for token in iterable:
            if token.kind.preamble is not None:
                self.process(Token(x, "") for x in token.kind.preamble)
            if isinstance(token.kind, FormalOperand):
                self._push_operand(Tree(token))
            elif isinstance(token.kind, FormalOperator):
                while token.kind.left_arity != 0 and self.operator_stack and \
                        self.operator_stack.top().kind.priority <= token.kind.priority \
                        and self._op_dryrun():
                    self._op()
                self.operator_stack.push(token)
                self.operand_stack.push(self.SEP)
                if token.kind.right_arity == 0: self._op()
            else:
                raise ParseError(token, "unrecognized token")
    
    def _op(self):
        """(internal) Pops one operator off the stack, as well as its operands,
        and pushes the result to the operand stack."""
        op = self.operator_stack.pop()
        try:
            right = self._pop_operands(op.kind.right_arity, op.kind.right_mandatory)
            if self.operand_stack.pop() is not self.SEP:
                raise ValueError, "too many operands"
            left = self._pop_operands(op.kind.left_arity, op.kind.left_mandatory)
            self._push_operand(Tree(op, left+right))
        except ValueError, v:
            raise ParseError(op, v)   
    
    def _op_dryrun(self):
        """(internal) Checks whether there exist enough right-hand-side
        operators for _op() to succeed.
        @return True iff the number of operands on top of the stack is suitable.
        """
        op = self.operator_stack.top()
        r, l = self._depth2()
        if op.kind.right_mandatory <= r <= op.kind.right_arity:
            return r + l > 0
        else:
            return False
    
    def _pop_operands(self, at_most, at_least):
        """(internal) Pops 'at_least' to 'at_most' operands."""
        if at_most == FormalOperator.GREEDY: return self._pop_greedy()
        ob = []
        while self.operand_stack and self.operand_stack.top() is not self.SEP \
                and len(ob) < at_most:
            ob.append(self.operand_stack.pop())
        if len(ob) < at_least:
            raise ValueError, "not enough operands"
        ob.reverse()
        return ob

    def _push_operand(self, operand):
        while self.operator_stack and \
                self.operator_stack.top().kind.right_arity == self._depth():
            self._op()
        self.operand_stack.push(operand)
    
    def _pop_greedy(self):
        """(internal) Pops as many operands as are negotiable."""
        ob = []
        while self.operand_stack and self.operand_stack.top() is not self.SEP:
            ob.append(self.operand_stack.pop())
        ob.reverse()
        return ob
    
    def _depth(self):
        return self._drill(self.operand_stack, self.SEP)
    
    def _depth2(self):
        i1 = self._depth()
        i2 = self._drill(self.operand_stack[:-(i1+1)], self.SEP)
        return i1, i2
    
    @staticmethod
    def _drill(stack, sep):
        for i in xrange(len(stack)):
            if stack[-(i+1)] is sep:
                return i
        return len(stack)

    def result(self):
        while self.operator_stack: self._op()
        r = self.operand_stack.pop()
        if len(self.operand_stack) > 0:
            raise ParseError(r.root, "missing operator")
        else:
            return r


if __name__ == "__main__":
    plus = FormalOperator(3, 1, 1)
    mul = FormalOperator(2, 1, 1)
    eq = FormalOperator(9, 1, 0)
    minus = FormalOperator(3, 0, 1)
    num = FormalOperand()
    lexer = {'+': plus, '*': mul, '-': minus, '=': eq}
    input = [Token(lexer.get(c, num), c) for c in "5*-1+7*9*2="] 
    c = Calculator()
    c.process(input)
    print c.operand_stack
    print c.operator_stack
